This invention relates to computer software compilation systems, and more specifically to a compiler that performs interprocedural analysis and optimization.
A. Compilers and Interprocedural Analysis (IPA)
A program comprises one or more external source code files. Each source code file contains one or more translation units. A translation unit is a subroutine, function, or other separately compilable software entity. A compiler translates a program to one or more object files. In particular, a compiler compiles the source files of a program one at a time. For each source file, the compiler works on one translation unit at a time and generates a corresponding object file. The developer does not have to compile an entire program at one time, but rather, can compile the program in separate pieces as it is developed. After an entire program is compiled, a linkage editor processes all of the object files of the program and generates an executable program. Therefore, in a conventional compilation system, a developer invokes two separate steps: a compilation step and a link step.
There are two major phases of a compiler: a front end and a back end. The front end of a compiler consists of those phases that depend on the source language and are largely independent of the target computer. The front end typically performs lexical and syntactic analysis, creates the symbol table, performs semantic analysis, and generates intermediate code which is an intermediate representation of the source code.
The back end of a compiler includes those phases of compilation that depend on the target computer and generally do not depend on the source language, but depend on the intermediate code. The back end typically performs code optimization on the intermediate representation and generates the target object files.
A disadvantage of a conventional compilation system is that during compilation the compiler only has local information about the translation unit on which the compiler is currently working. The compiler does not have any global information pertaining to the entire program or to the relationships between the translation units of the program. Because of this lack of global information, the back end of the compiler is unable to perform certain optimizations, such as optimizing the operations involving global variables and the passing of constant parameters.
A well known technique that solves this disadvantage of conventional compilation systems is interprocedural analysis (IPA). IPA is a phase that is added to a compilation system to analyze an entire program and collect global information related to the translation units. Global information includes global variables and how the multiple translation units manipulate and reference the global variables. Once the global information is collected, it is then passed to the optimizer as part of the back end of the compilation system. Thus, when the optimizer optimizes a translation unit, the optimizer accesses this global information and performs additional and more aggressive optimization pertaining to global variables. IPA improves the efficiency of the generated object code by providing optimization at a global level, thereby improving the run-time performance of the executable program.
Existing IPA analysis defers analysis and optimization of a program until link time, at which time all translation units are effectively merged into one big aggregate translation unit, which is then analyzed and optimized. This means that if the programmer edits a single translation unit, the entire program must be reanalyzed and reoptimized. Furthermore, existing IPA analysis, by creating a monolithic translation unit, prevents distributed compilation of translation units by multiple processors.